package com.lims.algorithm.algset.graph.basic;

import java.util.Deque;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * <功能简述> 邻接矩阵表示图 抽象类
 *
 * @author lims
 * @date 2020-08-19 10:52
 */
public abstract class GraphMatrixAbs<T> extends GraphAbs<T> {
    /**
     * 邻接矩阵
     */
    protected int[][] edges;
    /**
     * 边的数目
     */
    protected int eNum;
    /**
     * 记录被访问了的节点
     */
    public boolean[] isVisited;

    public int geteNum() {
        return eNum;
    }

    public void seteNum(int eNum) {
        this.eNum = eNum;
    }

    public boolean[] getIsVisited() {
        return isVisited;
    }

    public void setIsVisited(boolean[] isVisited) {
        this.isVisited = isVisited;
    }

    @Override
    protected int getPosition(T ch) {
        for (int i = 0; i < vertes.length; i++) {
            if (vertes[i].equals(ch)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public void print() {
        System.out.printf("Martix GraphUDG:\n");
        for (int i = 0; i < vertes.length; i++) {
            for (int j = 0; j < vertes.length; j++) {
                System.out.printf("%d ", edges[i][j]);
            }
            System.out.printf("\n");
        }
    }

    /**
     * 返回顶点值
     *
     * @param i
     * @return
     */
    private T getValue(int i) {
        return vertes[i];
    }

    /**
     * 找到本节点的第一个邻接节点
     *
     * @param index
     * @return
     */
    private int getFirstAjcNode(int index) {
        for (int j = 0; j < vertes.length; j++) {
            if (edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 找出本节点的下一个邻接节点
     *
     * @param v1 本节点
     * @param v2 当前邻接节点
     * @return
     */
    private int getNextAjcNode(int v1, int v2) {
        for (int j = v2 + 1; j < vertes.length; j++) {
            if (edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 深度优先遍历
     */
    @Override
    public void DFS() {
        for (int i = 0; i < vertes.length; i++) {
            if (!isVisited[i]) {
                DFS(isVisited, i);
            }
        }
    }

    private void DFS(boolean[] isVisited, int i) {
        System.out.print(getValue(i) + "->");
        isVisited[i] = true;
        int ajc = getFirstAjcNode(i);
        while (ajc != -1) {
            if (!isVisited[ajc]) {
                DFS(isVisited, ajc);
            }
            ajc = getNextAjcNode(i, ajc);
        }
    }

    /**
     * 广度优先遍历
     */
    @Override
    public void BFS() {
        // 遍历所有节点进行BFS
        for (int i = 0; i < vertes.length; i++) {
            if (!isVisited[i]) {
                BFS(isVisited, i);
            }
        }
    }

    private void BFS(boolean[] isVisited, int i) {
        // 队列头
        int h;
        // 邻接节点
        int ajc;

        Deque<Integer> deque = new LinkedBlockingDeque<>();
        System.out.print(getValue(i) + "->");
        isVisited[i] = true;
        deque.offerLast(i);
        while (!deque.isEmpty()) {
            h = deque.pollFirst();
            ajc = getFirstAjcNode(h);
            while (ajc != -1) {
                if (!isVisited[ajc]) {
                    System.out.print(getValue(ajc) + "->");
                    isVisited[ajc] = true;
                    deque.offerLast(ajc);
                }
                ajc = getNextAjcNode(h, ajc);
            }
        }
    }
}
